This invention relates to the architecture of computer systems, and in particular to an asynchronous computer system in which a counterflow pipeline processor architecture is partitioned into functionally distinct, interconnected "layers" for faster processing of data flowing through the pipeline.
A counterflow pipeline consists of a number of stages through which two streams of digitally encoded "words" flow in opposite directions. The words can be considered data items and may include instructions, data, or both. For explanation here, we call the opposite directions North and South. It is a defining property of counterflow pipelines that every Northward-flowing word and every Southward-flowing word concurrently present in the pipeline encounter each other exactly once in some stage of the pipeline.
Counterflow pipeline processors are now well known. See, e.g., U.S. Pat. No. 5,572,690, entitled "Cascaded Multistage Counterflow Processor for Carrying Distinct Data in Two Opposite Directions." In a counterflow pipeline processor, the encoded words are of two kinds: data words and instruction words. Data words typically consist of one or more data portions each encoding a data value, and a like number of reference portions, such as an address or tag, each identifying a corresponding data portion within the data word. Instruction words typically consist of an operation portion which specifies a processing step to be performed, and one or more operand-reference portions together with a like number of portions for holding encoded data. Operand-reference portions identify those data portions of words of either kind that are to participate in, or be affected by, the specified operation. In our implementation, instruction words flow only Northward, and data words flow only Southward.
The stages of the counterflow pipeline may ignore some or all parts of any word, working only on selected parts of others. Also, the stages may examine reference parts of the word, and may change the "active" parts of words, or may pass words along unmodified.
The counterflow pipeline stages modify the active parts of certain Northbound and/or Southbound words using information taken from either or both streams. As the words flow, Northbound and Southbound items encounter one another in particular stages of the counterflow pipeline. The stage may change the active parts of a word of either kind, using information contained in any part of that word itself, or according to information from the reference or active parts of a word encountered in the oppositely flowing stream.
To accomplish this task the pipeline must ensure that each and every Southbound word encounters each and every Northbound word in some stage. When a Northbound and a Southbound word encounter each other in some stage, we call them an "encounter pair." In which stage the words encounter each other is not important, but it is essential that each and every Northbound element encounter each and every Southbound element in some stage. The invention described below provides a structure for achieving that result efficiently.